import javax.jnlp.ClipboardService;
import java.util.*;

public class project {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        movePlant(A.size(),A,B,C);
    }
    public void movePlant(int size,List<Integer> one,List<Integer> two,List<Integer> three){
        if(size==1){
            three.add(one.remove(one.size()-1));
            return;
        }
        movePlant(size-1,one,three,two);
        three.add(one.remove(size-1));
        movePlant(size-1,two,one,three);
    }










    public int getLucky(String s, int k) {
        StringBuilder sb=new StringBuilder();
        for(char ch : s.toCharArray()){
            sb.append(ch-'a'+1);
        }
        s=sb.toString();
        while(k>0){
            int tmp=0;
            for(char ch : s.toCharArray()){
                tmp+=ch-'0';
            }
            s=String.valueOf(tmp);
            k--;
        }
        return Integer.parseInt(s);
    }







    public int[][] construct2DArray(int[] original, int m, int n) {
        if(m*n<original.length||m*n>original.length){
            return new int[][]{};
        }
        int[][] arr=new int[m][n];
        int k=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(k<original.length){
                    arr[i][j]=original[k++];
                }else{
                    break;
                }
            }
        }
        return arr;
    }










    public int findMiddleIndex(int[] nums) {
        int len=nums.length;
        int[] arr=new int[len];
        arr[0]=nums[0];
        for(int i=1;i<len;i++){
            arr[i]=nums[i]+arr[i-1];
        }
        for(int i=0;i<len;i++){
            if(arr[i]-nums[i]==arr[len-1]-arr[i]){
                return i;
            }
        }
        return -1;
    }








    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        List<Integer> arr=new ArrayList<>();
        Set<Integer> set1=new HashSet<>();
        Set<Integer> set2=new HashSet<>();
        Set<Integer> set3=new HashSet<>();
        for(int n :nums1){
            set1.add(n);
        }
        for(int n :nums2){
            set2.add(n);
        }
        for(int n :nums3){
            set3.add(n);
        }
        Set<Integer> set=new HashSet<>();
        set.addAll(set1);
        set.addAll(set2);
        set.addAll(set3);
        for(int n : set){
            int t1= set1.contains(n) ?1:0;
            int t2= set2.contains(n) ?1:0;
            int t3= set3.contains(n) ?1:0;
            if(t1+t2+t3>=2){
                arr.add(n);
            }
        }
        return arr;
    }














    public boolean areNumbersAscending(String s) {
        String[] str=s.split(" ");
        int a=0;
        int b=0;
        int i=0;
        for(String s1 : str){
            if(s1.charAt(i)<'0'||s1.charAt(i)>'9') {
                continue;
            }
            a=Integer.parseInt(s1);
            if(b!=0){
                if(b>=a){
                    return false;
                }
            }
            b=a;
        }
        return true;
    }









    public int countLargestGroup(int n) {
        Map<Integer,Integer> map=new HashMap<>();
        int max=0;
        for(int i=1;i<=n;i++){
            int tmp=i;
            int set=0;
            while(tmp!=0){
                set+=tmp%10;
                tmp/=10;
            }
            map.put(set,map.getOrDefault(set,0)+1);
            max=Math.max(map.get(set),max);
        }
        int count=0;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue()==max){
                count++;
            }
        }
        return count;
    }













    public int[][] transpose(int[][] matrix) {
        int[][] arr=new int[matrix[0].length][matrix.length];
        for(int i=0;i< matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                arr[j][i]=matrix[i][j];
            }
        }
        return arr;
    }







    public int findLucky(int[] arr) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<arr.length;i++){
            if(map.containsKey(arr[i])){
                map.put(arr[i], map.get(arr[i])+1);
            }else{
                map.put(arr[i],1);
            }
        }
        int max=-1;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue()==entry.getKey()){
                max=Math.max(entry.getValue(),max);
            }
        }
        return max;
    }







    public int removePalindromeSub(String s) {
        if(s.equals(" ")){
            return 0;
        }
        if(s.equals(new StringBuffer(s).reverse().toString())){
            return 1;
        }
        return 2;
    }







    public int minDeletionSize(String[] strs) {
        int count=0;
        for(int i=0;i<strs[0].length();i++){
            for(int j=0;j<strs.length-1;j++){
                if(strs[j].charAt(i)>strs[j+1].charAt(i)){
                    count++;
                    break;
                }
            }
        }
        return count;
    }











    public int minStartValue(int[] nums) {
        int startValue=Integer.MAX_VALUE;
        int sum=0;
        for(int n : nums){
            sum+=n;
            startValue=Math.min(sum,startValue);
        }
        if(startValue>=1){
            return 1;
        }else{
            return 1-startValue;
        }
    }
}
